#define DEBUG
#include <cstdio>

using namespace std;

const int maxn=100000, maxk=16, maxm=10, maxw=100000;

int max(int a, int b) {
  return a>b ? a : b;
}

class Trie {
public:
  Trie *son[26]={};
  int v=0;

  void addStr(Trie *last, char *o) {
    if (last) {
      v = last->v;
      for (int i=0; i<26; i++) {
        son[i] = last->son[i];
      }
    }
    if (*o) {
      int t=*o-'a';
      son[t] = new Trie();
      son[t]->addStr(last ? last->son[t] : 0, o+1);
    } else {
      v++;
    }
  }
};

int check(Trie *a, Trie *b, Trie *c, char *s, int dep=0) {
  int ret=0;
  if ((a ? a->v : 0)+(b ? b->v : 0)-2*(c ? c->v : 0)) {
    ret = dep;
  }

  if (*s) {
    int t=*s-'a';
    if ((a && a->son[t]) || (b && b->son[t])) {
      ret = max(ret, check(a ? a->son[t] : 0, b ? b->son[t] : 0, c ? c->son[t] : 0, s+1, dep+1));
    }
  }
  return ret;
}

class Tree {
public:
  int f[maxn+1][maxk+1], bro[maxn+1], son[maxn+1], dep[maxn+1];
  Trie *trie[maxn+1];
  char m[maxn+1][maxm+1];

  void addSide(int fa, int s) {
    bro[s] = son[fa], f[s][0] = fa;
    son[fa] = s;
  }

  void build(int o) {
    dep[o] = dep[f[o][0]]+1;
    trie[o] = new Trie();
    trie[o]->addStr(trie[f[o][0]], m[o]);
    for (int i=1; i<=maxk; i++) {
      f[o][i] = f[f[o][i-1]][i-1];
    }
    for (int i=son[o]; i; i=bro[i]) {
      build(i);
    }
  }

  int lca(int u, int v) {
    if (dep[u]<dep[v]) {
      int t;
      t=u, u=v, v=t;
    }

    for (int i=maxk; i>=0; i--) {
      if (dep[f[u][i]]>=dep[v]) u=f[u][i];
    }
    if (u==v) return u;
    for (int i=maxk; i>=0; i--) {
      if (f[u][i]!=f[v][i]) u=f[u][i], v=f[v][i];
    }
    return f[u][0];
  }
};

int main() {
#ifdef DEBUG
  freopen("src.in", "r", stdin);
  freopen("src.out", "w", stdout);
#endif

  static Tree tree;
  int n, o;
  scanf("%d %d", &n, &o);
  for (int i=1; i<=n; i++) {
    scanf("%s", tree.m[i]);
  }
  for (int i=2; i<=n; i++) {
    int f;
    scanf("%d", &f);
    tree.addSide(f, i);
  }
  tree.build(1);

  int q, ans=0;
  scanf("%d", &q);
  for (int i=1; i<=q; i++) {
    int s, t;
    char w[maxw+1];
    scanf("%d %d %s", &s, &t, w);
    s^=o*ans, t^=o*ans;

    int u=tree.lca(s, t);
    ans=0;
    for (int j=0; w[j]; j++) {
      ans = max(ans, check(tree.trie[s], tree.trie[t], tree.trie[tree.f[u][0]], w+j));
    }
    printf("%d\n", ans);
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}
